import java.util.*;

/**
 * Created by L.jp
 * Description:字典wordList 中从单词 beginWord和 endWord 的 转换序列 是一个按下述规格形成的序列：
 *
 * 序列中第一个单词是 beginWord 。
 * 序列中最后一个单词是 endWord 。
 * 每次转换只能改变一个字母。
 * 转换过程中的中间单词必须是字典wordList 中的单词。
 * 给你两个单词 beginWord和 endWord 和一个字典 wordList ，找到从beginWord 到endWord 的 最短转换序列中的单词数目 。
 * 如果不存在这样的转换序列，返回 0。

 输入：beginWord = "hit"
      endWord = "cog"
      wordList = ["hot","dot","dog","lot","log","cog"]
 输出：5
 解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

 * User: 86189
 * Date: 2021-11-30
 * Time: 17:02
 */
/*
    思路:（最短路径问题，采用广度优先搜索，利用队列）
    1.由于字典链表查询速度不快，所以改成字典哈希表，查询速度会快很多，将字典链表中的字符串加入到字典哈希表中
    2.在遍历这些字典哈希表中，有的字符串可能已经遍历过了，为了避免重复查询，所以需要创建一个存放被访问过的哈希表
    3.由于开头字符串也算一步，所以首先将开头字符串加入到已经访问过的哈希表中，创建一个队列，临时存放转换的字符串且存在字典哈希表中
    4.创建一个记录步数的变量，初始步数为1，
    5.接着去遍历第一个字符串，也就是开头字符串，怎么样让它从本身的字符串一步步变成最终的字符串呢，那就是对每个字符串的三个字母，每个字母从a到z变换查询
    6.如果在变换的过程中，字典哈希表中不存在这个变换的字符串或者被访问过的哈希表中存在这个字符串，那么直接跳过这个字符串，去判断下一个
    7.如果这个转换的字符串等于最终的字符串，那么就直接返回之前记录的步数+1
    8.如果字典哈希表中存在这个字符串，而且被访问的哈希表中不存在这个字符串，那么就加入到队列中，也将这个字符串加入到被访问过的哈希表中，表示已经访问过了
    9.每在队列中弹出的一个字符串经过一系列转换和判断是否存在，就让步数+1,也就是每弹出一个字符串经过一系列判断都要步数+1；
    10.最终队列为空时，表示没有可以判断的字符串了，返回0；
 */
public class WordChain {
    public static int ladderLength(String beginWord, String endWord, List<String> wordList) {
        //存放字典列表里面的单词，以便查询，hash表查询更快
        Set<String> wordSet=new HashSet<>();
        for(String word:wordList){
            wordSet.add(word);
        }
        Set<String> visitedSet=new HashSet<>();
        visitedSet.add(beginWord);//将访问过的单词加入到被访问过的哈希表中，以便查询访问过的单词
        Queue<String> q=new LinkedList<>();//存放字典里面可以经过变换得到的单词
        q.offer(beginWord);//先存放开头单词
        int step=1;//一开始的开头单词也算一步
        while(!q.isEmpty()){
            int qSize=q.size();
            //转换一个单词
            while(qSize!=0){
                String cur=q.peek();
                q.poll();
                qSize--;
                //对弹出字符串的每个字母进行转换
                for(int i=0;i<cur.length();i++){
                    //每一次的弹出的字符串都要先转换成可拼接的字符串
                    StringBuilder curb=new StringBuilder(cur);//把当前队列弹出的队头字符串转换成StringBuilder,用于以后改变字符串
                    //每个字母变换都从a到z区间去找
                    for(char ch= 'a';ch<='z';ch++){
                        curb.setCharAt(i,ch);//把每个字母改成从a到z的任意一个，在后面去判断他是不是在字典哈希表中
                        String curbStr=curb.toString();
                        if(!wordSet.contains(curbStr) || visitedSet.contains(curbStr)){
                            continue;//如果转换的字符串不存在字典哈希表中或者已经被访问过了，那么直接跳过
                        }
                        //如果存在字典哈希表中，或者没有被访问过，在这个基础上，如果这个字符串和目标字符串相等，那么直接返回之前加的步数+1;
                        if(curbStr.equals(endWord)){
                            return step+1;//在25个字母转换过程中，找到了最终的单词，那么直接返回一开始的step+1;
                        }
                        //字典哈希表中包含这个变换的字符串，而且在重复的哈希表中也没有这个字符串，那么就将这个字符串入队和入重复的哈希表
                        visitedSet.add(curbStr);
                        q.add(curbStr);
                    }
                }
            }
            //每转换一个单词就要加步数
            step++;
        }
        //队列里面没有要转换的字符串了，转换不成功，返回0
        return 0;
    }

    public static void main(String[] args) {
        String beginWord="hit";
        String endWord="cog";
        List<String> list=new ArrayList<>();
        list.add("hot");
        list.add("dot");
        list.add("dog");
        list.add("lot");
        list.add("log");
        list.add("cog");
        System.out.println(ladderLength(beginWord, endWord, list));
    }

}
